Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: 4Sum II

Problem Statement

Given four arrays of integers nums1, nums2, nums3, and nums4 of the same length n, return the count of tuples (i, j, k, l) such that:

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Examples

Example 1:

  • Input: nums1 = [1], nums2 = [-1], nums3 = [0], nums4 = [0]
  • Expected Output: 1
  • Justification: The one quadruplet that sum up to 0 is:
    • (1, -1, 0, 0)

Example 2:

  • Input: nums1 = [0, 1], nums2 = [1, -1], nums3 = [-1, 0], nums4 = [1, -1]
  • Expected Output: 4
  • Justification: The four quadruplets that sum up to 0 are:
    • (0, 1, 0, -1)
    • (0, -1, 0, 1)
    • (1, -1, -1, 1)
    • (1, 1, -1, -1)

Example 3:

  • Input: nums1 = [-1, 3], nums2 = [2, -3], nums3 = [3, 4], nums4 = [-4, -3]
  • Expected Output: 3
  • Justification: The three quadruplets that sum up to 0 are:
    • (-1, 2, 3, -4)
    • (3, -3, 4, -4)
    • (3, -3, 3, -3)

Solution

To solve this problem, we'll leverage a hash map to efficiently find pairs that sum up to the target value, which is zero in this case. The rationale behind using a hash map is to store the sum of pairs from the first two arrays along with their frequency. This way, we can quickly look up the complement of these sums in the hash map when iterating through pairs from the last two arrays. This approach significantly reduces the time complexity compared to a brute force solution, which checks every possible quadruplet.

The effectiveness of this approach lies in its ability to transform the problem from a four-array problem into two, two-array problems, thereby simplifying the process of finding the target sum. By focusing on sums rather than individual elements, we can more easily identify combinations that meet our criteria, making this method both efficient and scalable for larger input sizes.

Step-by-Step Algorithm

  1. Initialize a Hash Map: Create an empty hash map (sumMap) to store the sum of each pair from nums1 and nums2 as keys and their frequency (number of times the sum occurs) as values.

  2. Compute Sums of Pairs from nums1 and nums2:

    • Iterate over each element in nums1 using a loop.
    • For each element in nums1, iterate over each element in nums2 using another loop.
    • Calculate the sum of the current elements from nums1 and nums2.
    • Update sumMap with this sum. If the sum already exists as a key in sumMap, increment its value by 1. Otherwise, add the sum as a new key with the value of 1.
  3. Count Quadruplets:

    • Initialize a counter (count) to 0. This will track the number of quadruplets that sum to 0.
    • Iterate over each element in nums3 using a loop.
    • For each element in nums3, iterate over each element in nums4 using another loop.
    • For the current elements from nums3 and nums4, calculate the sum that would be needed from nums1 and nums2 for the total four elements to sum to 0. This is the negation of the sum of the current elements from nums3 and nums4.
    • Check if this required sum exists as a key in sumMap. If it does, add the corresponding value (frequency) from sumMap to count.
  4. Return Result: Return the count variable, which now contains the total number of quadruplets that sum to 0.

Algorithm Walkthrough

Let's consider the Input: nums1 = [0, 1], nums2 = [1, -1], nums3 = [-1, 0], nums4 = [1, -1].

  1. Initialize sumMap: Let's start with an empty hash map.

  2. Compute Sums of Pairs from nums1 and nums2:

    • Pair 0 from nums1 with 1 from nums2 to get sum 1. Update sumMap: {1: 1}.
    • Pair 0 from nums1 with -1 from nums2 to get sum -1. Update sumMap: {1: 1, -1: 1}.
    • Pair 1 from nums1 with 1 from nums2 to get sum 2. Update sumMap: {1: 1, -1: 1, 2: 1}.
    • Pair 1 from nums1 with -1 from nums2 to get sum 0. Update sumMap: {1: 1, -1: 1, 2: 1, 0: 1}.
  3. Count Quadruplets:

    • Pair -1 from nums3 with 1 from nums4. The required sum from nums1 and nums2 is 0 (since -1 + 1 = 0, we need 0 from nums1 and nums2 to sum to 0). sumMap has 0: 1, so increment count by 1.
    • Pair -1 from nums3 with -1 from nums4. The required sum is 2. sumMap has 2: 1, so increment count by 1.
    • Pair 0 from nums3 with 1 from nums4. The required sum is -1. sumMap has -1: 1, so increment count by 1.
    • Pair 0 from nums3 with -1 from nums4. The required sum is 1. sumMap has 1: 1, so increment count by 1.
  4. Return Result: The final count is 4, indicating there are 4 quadruplets across the four arrays that sum to 0.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • Computing Sums of Pairs: The first part of the algorithm involves iterating over two loops to compute the sums of elements from nums1 and nums2, and then from nums3 and nums4. Each pair of arrays involves operations where (n) is the length of the array. Since we do this for two pairs of arrays, the time complexity for this part is .
  • Looking Up Sums: The second part involves looking up the negative of these sums in the hash map for pairs from nums3 and nums4. This also results in operations, but the lookup time is on average for hash maps, leading to for this part.

The overall time complexity of the algorithm is therefore .

Space Complexity

  • Hash Map Storage: The space complexity is primarily due to the storage of sum frequencies in a hash map. In the worst case, all pair sums are unique, leading to space complexity due to the storage of these sums.

Therefore, the overall space complexity of the algorithm is .

4Sum II (medium)
Furthest Building You Can Reach (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity